\section{线性 Diophantus 方程}

\begin{frame}{二元一次不定方程}
古希腊的 Diophantus(丢番图) 著 Arithmetica (《算术》) 对这类方程的研究最
具影响， 故此命名。 其最显著的特点是只求整数解 (或有理数解), 这使得它与一般方程 (例如求实数解) 截然不同。 因其解一般不是唯一的， 故也称为\emph{不定方程}。 
\pause
最著名的例子是 Fermat 方程 $x^{n}+y^{n}=z^{n}$ ($n \geqslant 3$). 而 $n=2$ 时， 此即是求勾股数的方程。 
\pause
求 Bézout 等式 $u a+v b=d$ 的系数 $u, v$ 也是解不定方程。

\pause
\begin{theorem}%定理1
  [二元一次不定方程] \label{二元一次不定方程}
  设 $a, b, c$ 为非零整数， 考虑方程
\[
  a x+b y=c.
\]
\pause
令
 \[
   (a, b)=d, \quad a^{\prime}=a / d,\quad  b^{\prime}=b / d,  \quad c^{\prime}=c / d.
 \]

 \pause
 (1) 此方程有整数解当且仅当 $d \mid c$; 有解时与 $a^{\prime} x+b^{\prime} y=c^{\prime}$ 同解，其中 
 且可由辗转相除得到方程的一个解。

 \pause
  (2) 若方程有一整数解 $x=x_{0}, y=y_{0}$, 则方程的全部整数解为
\[
x=x_{0}+k b^{\prime}, \quad y=y_{0}-k a^{\prime} \quad\text { (对整数 $k$). }
\]
\end{theorem}

\end{frame}

\begin{frame}
\begin{example}%例1
求 $434 x+182 y=42$ 的整数解。
\end{example}

\pause
\begin{solution*}%解
相当于定理 1 中 $a=434, b=182, c=42$. 而 $d=(a, b)=(434,182)=(217,91) \cdot 2=14$ (由 \S1.2 例 1) , $14 \mid 42$, 故知方程有解。 
\pause
且原方程与如下方程同解：
\[
  31 x+13 y=3.
\]
\pause
由 \S1.2 例 1 知， 经过辗转相除得到 Bézout 等式
\[
  -31 \cdot 5+13 \cdot 12=1.
\]
故
\[
  -31 \cdot 15+13 \cdot 36=3.
\]
故得原方程一解： $x_{0}=-15, y_{0}=36$. 
\pause
故原方程的全部解为
\[
  x=-15+13 k, \quad y=36-31 k\quad (k\in \ZZ).
\]
\end{solution*}
\end{frame}



\begin{frame}
  \begin{proof*}[定理~\ref{二元一次不定方程}~的证明]
 (1) 若方程有整数解 $x_{0}, y_{0}$, 即 $a x_{0}+b y_{0}=c$, 则 $d$ 整除左边， 故 $d \mid c$. 反之， 若 $d \mid c$, 则由 Bézout 等式 $u a+v b=d$, 两边同乘 $c^{\prime}$, 得 $c^{\prime} u a+c^{\prime} v b=c$,则得到原方程解
 \[
   x=c^{\prime} u, \quad y=c^{\prime} v.
 \]

 (2) 将 $a x_{0}+b y_{0}=c$ 两边除以 $d$, 化为
  \[
    a^{\prime} x_{0}+b^{\prime} y_{0}=c^{\prime},
\]
故对任意整数 $k$ 有
\[
  a^{\prime}\left(x_{0}+k b^{\prime}\right)+b^{\prime}\left(y_{0}-k a^{\prime}\right)=c^{\prime}.
\]
再乘 $d$ 得 $a\left(x_{0}+k b^{\prime}\right)+b\left(y_{0}-k a^{\prime}\right)=c$, 即知 $x=x_{0}+k b^{\prime}, y=y_{0}-k a^{\prime}$ 为原方程解。

反之， 若 $a x+b y=c$, 除以 $d$ 则得 $a^{\prime} x+b^{\prime} y=c^{\prime}$, 与 $a^{\prime} x_{0}+b^{\prime} y_{0}=c^{\prime}$ 相减， 得
\[
  a^{\prime}\left(x-x_{0}\right)=-b^{\prime}\left(y-y_{0}\right).
\]
故 $b^{\prime}\mid \left(x-x_{0}\right), a^{\prime}\mid \left(y-y_{0}\right)$, 设 $\left(x-x_{0}\right)=k b^{\prime},\left(y-y_{0}\right)=m a^{\prime}$, 由上式知 $k a^{\prime} b^{\prime}=-m a^{\prime} b^{\prime}$, 故 $m=-k$. 即知 $x=x_{0}+k b^{\prime}, y=y_{0}-k a^{\prime}$.
\end{proof*}
\end{frame}



\begin{frame}{多元一次不定方程}

 \begin{example}%例2
 求 $434 x+182 y+10 z=4$ 的整数解。
 \end{example}

 \begin{solution*}%解
   我们已经知道形如$ax+by=c$的Diophantus方程如何解。我们想把问题转化为
   形如$ax+by=c$的方程构成的方程组。
   \pause
   引入中间变量$t'$, 令
   \[
     434x+182y=t',\quad t'+10z=4. 
 \]
 \pause
 注意到$(434, 182)=14$, 我们可设$t'=14t$. 
 \pause
   这样我们可以写出方程组
   \[
     \begin{cases}
       434x+182y=14t\\
       14t+10z=4,
     \end{cases}
     \quad \text{或者}\quad
     \begin{cases}
       31x+13y=t\\
       7t+5z=2.
     \end{cases}
   \]
   \pause
   接下来我们从后往回解右边的方程组。
   先看第二个方程。显然$t=1, z=-1$是一个整数解。
   由定理1知所有整数解形如
   \[
     t=1+5m,\quad z=-1-7m\quad (m\in \ZZ).
   \]
   \pause
  再把$t=1+5m$代入来解第一个方程。
  B\'ezout等式$-31\cdot 5 + 13\cdot 12=1$告诉我们一个特解为
  $x=-5t=-5(1+5m)=-5-25m, y=12t=12(1+5m)=12+60m$.
\end{solution*}
\end{frame}

\begin{frame}
  \begin{solution*}[解 (续)]
  进而由定理1知所有整数解为
  \[
    x=-5-25m+13k,\quad y=12+60m-31k \quad (k\in \ZZ).
  \]
  \pause
  这样方程组的解形如
  \[
  x=-5-25 m+13 k, \quad y=12+60 m-31 k, \quad z=-1-7 m\quad (m,k\in \ZZ).
  \]
  这些就是$434 x+182 y+10 z=4$的全部解。
% $d=(434,182,10)=(217,91,5) \cdot 2=(7,5) \cdot 2=2$ (由 \S1.2 例 1), 故方程有解。 原方程同解于
% \[
% 217 x+91 y+5 z=2.
% \]
% 分别求解
% \[
% 217 x+91 y=7 t_{2} \quad \text { 与 }\quad 7 t_{2}+5 z=2 .
% \]
% 由例 1 , 有 Bézout 等式 $-217 \cdot 5+91 \cdot 12=7$ 和 $-7 \cdot 2+5 \cdot 3=1$, 得上两方程 全部解为
% \[
% x=-5 t_{2}+13 k, \quad y=12 t_{2}-31 k ; \quad t_{2}=-4+5 m, \quad z=6-7 m
% \]
% 故原方程的全部解为
% \[
%   x=20-25 m+13 k, \quad y=-48+60 m-31 k, \quad z=6-7 m\quad \text{( $k, m$ 为任意整数).}
% \] 
 \end{solution*}

 \pause
 \begin{theorem}%定理2
[多元一次不定方程] 设 $a_{1}, \cdots, a_{s}, n$ 为非零整数， 则方程
  \[
  a_{1} x_{1}+\cdots+a_{s} x_{s}=n
\]
有整数解当且仅当 $\left(a_{1}, \cdots, a_{s}\right) \mid n$.
\end{theorem}

\pause
\begin{proof}
 记 $d=\left(a_{1}, \cdots, a_{s}\right)$. 若有整数 $x_{1}, \cdots, x_{s}$ 满足方程， 显然 $d$ 整除方程左边， 故 $d \mid n$. 反之， 设 $d \mid n$, 由 \S1.2 知道有 Bézout 等式 $u_{1} a_{1}+\cdots+u_{s} a_{s}=$ $d$, 两边乘 $n^{\prime}=n / d$, 即得到原方程的解。
%
% \pause
% 我们也可用数学归纳法， 证明 $d \mid n$ 时原方程有整数解。 当 $s=2$ 时已证 (定理 1). 假设对未知元个数小于 $s$ 的情形定理正确（这称为“归纳假设”), 要据此证明 $s$ 元情形定理成立。 原方程可写为
% \[
% \left(a_{1} x_{1}+a_{2} x_{2}\right)+a_{3} x_{3}+\cdots+a_{s} x_{s}=n
% \]
% 记 $d_{2}=\left(a_{1}, a_{2}\right)$, 则 $d=\left(d_{2}, a_{3}, \cdots, a_{s}\right)$. 我们知道， 形如 $a_{1} x_{1}+a_{2} x_{2}$ 的整数集恰为 $d_{2}$ 的倍数集 (\S1.2 系 2), 故原方程化为
% \[
%   \left\{\begin{array}{l}
%     a_{1} x_{1}+a_{2} x_{2}=d_{2} t_{2} \\
%     d_{2} t_{2}+a_{3} x_{3}+\cdots+a_{s} x_{s}=n.
% \end{array}\right.
% \]
 \end{proof}

 \end{frame}

 \begin{frame}

%   \begin{proof}[续]
% 此二方程的未知元个数都小于 $s$, 故由 “归纳法假设” 知它们都有整数解， 设它们的整数解各为 $x_{10}, x_{20}$ 与 $t_{20}, x_{30}, \cdots, x_{s 0}$. 代人方程即得
% \[
% \left(a_{1} x_{10}+a_{2} x_{20}\right)+a_{3} x_{30}+\cdots+a_{s} x_{s 0}=n
% \]
% 即得到原方程的解 $x_{10}, x_{20}, x_{30}, \cdots, x_{s 0}$. 证毕。
% \end{proof}
%
% \pause
   我们有了多元一次不定方程解的存在性的判定方法，不过上述证明并没有告诉我们求解。
 在实际求解时， 我们可以类似于例2那样求解，
 逐步考虑 $2,3, \cdots$ 个变元（课本上定理2的另一个证明正是展示了这个过程）。
 \pause
 以 $s=4$ 为例。 依次求出 
 \[
   \left(a_{1}, a_{2}\right)=d_{2},\quad \left(d_{2}, a_{3}\right)=d_{3},\quad
   \left(d_{3}, a_{4}\right)=d_{4}=d.
 \]
 \pause
 考虑方程
 \[
   \begin{cases}
   a_{1} x_{1}+a_{2} x_{2}=d_{2} t_{2} \\
 d_{2} t_{2}+a_{3} x_{3}=d_{3} t_{3} \\
 d_{3} t_{3}+a_{4} x_{4}=n.
 \end{cases}
 \]
 \pause
 从后向前依次求出各方程的所有解 (并将 $t_{i}$ 的值代人前一式), 则得到原方程的所有解。 
\pause
 不过， 因为每次求解的时候， 都是利用 $d_{i}$ 的 Bézout 等式 
 (例如 $d_{2} v_{2}+ a_{3} u_{3}=d_{3}$), 
 故可将 $t_{i}$ 看做参数 (常数) 而能求出各方程解的一般形式， 最后消去 $t_{i}$ 即得原方程的解。

 ~

 \pause
 \begin{comment*}%评述
 一次不定方程与 Bézout 等式关系密切。 不定方程既有悠久的历史，又与现代数学关系密切。 我们将在第五章进一步讨论不定方程， 在 \S2.5, \S3.4, \S6.4, \S6.6, 附录 5 讨论类似问题。
 \end{comment*}
 \end{frame}


 \begin{frame}{小结}
   \begin{enumerate}
     \item 叙述关于二元一次Diophantus方程$ax+by=c$的解的结论。存在性、求解、解集。
     \item 叙述多元一次Diophantus方程$a_1x_1+a_2x_2+\cdots+a_sx_s=n$的解的存在条件以及求解方法。
   \end{enumerate}
 \end{frame}
